package datastructure.book.dp._1_pathway.exercise.second;

import org.junit.jupiter.api.Test;

public class _2_Solution {
    /**
     * 一个机器人位于一个 m x n网格的左上角,
     * 网格中的障碍物和空位置分别用 1 和 0 来表示。机器人的移动路径中不能包含 任何 有障碍物的方格。
     * 机器人每次只能向下或者向右移动一步。
     * 机器人试图达到网格的右下角
     * 问总共有多少条不同的路径？
     * m ==obstacleGrid.length
     * n ==obstacleGrid[i].length
     * 1 <= m, n <= 100
     * obstacleGrid[i][j] 为 0 或 1
     *
     * 例如：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
     * 从左上角到右下角一共有 2 条不同的路径：
     * 1. 向右 -> 向右 -> 向下 -> 向下
     * 2. 向下 -> 向下 -> 向右 -> 向右
     *
     */
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        return 0;
    }

    /**
     * O(n)空间复杂度
     */
    @Test
    public void testUniquePathsWithObstacles2(){
        System.out.println(uniquePathsWithObstacles(new int[][]{
                {0,0,0}, {0,1,0}, {0,0,0}}));
    }
}
